Computer systems supporting priority-scheduled real-time threads or jobs need to guarantee low-latency dispatching of the real-time threads. Latency is the time taken from the instant at which a real-time event, such as an interrupt, occurs to the instant at which the real-time thread handling the event is executing so that the real-time thread is able to process the real-time event. General purpose multiprocessor computer systems, which guarantee low-latency for real-time threads, need to efficiently identify the real-time thread to handle the real-time event and efficiently dispatch the real-time thread to an appropriate processor.
Conventional computer systems supporting real-time threads typically achieve the required low-latency real-time thread dispatching by either restricting the workload the computer system handles by assuming embedded, special purpose kernels, or by statically partitioning a multiprocessor computer system such that some of the processors in the system are dedicated to real-time threads. Nevertheless, an embedded multiprocessor computer system is not feasible in a general purpose system in light of the ever-increasing multimedia-based software that relies on real-time aspects of a computer system. On the other hand, a statically partitioned multiprocessor system tends to waste resources due to the static partitioning.
Another previous general purpose multiprocessor system attempts to achieve low-latency real-time thread dispatching by maintaining a global queue which contains threads ordered by priority. Once a real-time thread becomes runnable as the result of the occurrence of a real-time event, the real-time thread is queued onto the global queue. The queued real-time thread immediately gets picked up by an idle processor, if such an idle processor is available. However, if none of the processors in the multiprocessor system are idle, then a suitable processor is selected as part of the dispatching algorithm. The selected processor is then interrupted to enable the selected processor to pick up the queued real-time thread.
In a general purpose multiprocessor system employing the above priority scheme, selecting an appropriate processor to process the queued real-time thread is a complex decision and must be performed carefully. To illustrate the complexity of the selection process, the following example scenario is provided. In the example, a two processor system includes one processor running a real-time thread (RT1) and a second processor running a non-real-time or time-share thread (TS1). If another real-time thread (RT2) becomes runnable due to the occurrence of a real-time event, RT2 should replace TS1 and not RT1. In this scenario, a dispatching algorithm must keep track of which processors are running real-time threads and which processors are running non-real-time threads. In general, each processor maintains the priority of the thread that the processor is currently executing to support correct scheduling of real-time threads. As part of dispatching, a real-time thread (RTx), a target processor is found by finding the processor (P) with the lowest priority (p). Then, RTx is switched onto P if the priority of RTx is greater than p. If a target processor cannot be found, then RTx is enqueued onto the global queue. Then, when a processor becomes idle, the idle processor is able to pick up RTx from the global queue.
This last described scheme of keeping track of priorities for each processor is very inefficient and slows the operation of the whole general purpose multiprocessor system. First, the priority needs to be updated every time a real-time thread is switched into and out of a processor. Second, when a target processor needs to be determined, the dispatching of a real-time thread includes looking at all the processors' priority to determine a suitable processor. Since multiple dispatches can occur simultaneously, care must be taken to avoid two different dispatches selecting the same processor. As a result, the accessing of priorities of the different processors must be synchronized, or suitable back off schemes must be executed in the event that the same processor is selected in two concurrent dispatches. Both of these techniques are inefficient. For example, the locking to maintain the priorities on thread switches can become contentious.
Therefore, for the reasons stated above, and for other reasons presented in greater detail in the Description of the Preferred Embodiments section of the present specification, there is a need for an improved low-latency real-time thread dispatching mechanism in a general purpose multiprocessor system.